
import os
from Crypto.Util.Padding import pad
from Crypto.Util.number import *
from Crypto.Cipher import AES
from gmpy2 import *

c1= 19024563955839349902897822692180949371550067644378624199902067434708278125346234824900117853598997270022872667319428613147809325929092749312310446754419305096891122211944442338664613779595641268298482084259741784281927857614814220279055840825157115551456554287395502655358453270843601870807174309121367449335110327991187235786798374254470758957844690258594070043388827157981964323699747450405814713722613265012947852856714100237325256114904705539465145676960232769502207049858752573601516773952294218843901330100257234517481221811887136295727396712894842769582824157206825592614684804626241036297918244781918275524254
c2= 11387447548457075057390997630590504043679006922775566653728699416828036980076318372839900947303061300878930517069527835771992393657157069014534366482903388936689298175411163666849237525549902527846826224853407226289495201341719277080550962118551001246017511651688883675152554449310329664415179464488725227120033786305900106544217117526923607211746947511746335071162308591288281572603417532523345271340113176743703809868369623401559713179927002634217140206608963086656140258643119596968929437114459557916757824682496866029297120246221557017875892921591955181714167913310050483382235498906247018171409256534124073270350
N= 21831630625212912450058787218272832615084640356500740162478776482071876178684642739065105728423872548532056206845637492058465613779973193354996353323494373418215019445325632104575415991984764454753263189235376127871742444636236132111097548997063091478794422370043984009615893441148901566420508196170556189546911391716595983110030778046242014896752388438535131806524968952947016059907135882390507706966746973544598457963945671064540465259211834751973065197550500334726779434679470160463944292619173904064826217284899341554269864669620477774678605962276256707036721407638013951236957603286867871199275024050690034901963
g1= 20303501619435729000675510820217420636246553663472832286487504757515586157679361170332171306491820918722752848685645096611030558245362578422584797889428493611704976472409942840368080016946977234874471779189922713887914075985648876516896823599078349725871578446532134614410886658001724864915073768678394238725788245439086601955497248593286832679485832319756671985505398841701463782272300202981842733576006152153012355980197830911700112001441621619417349747262257225469106511527467526286661082010163334100555372381681421874165851063816598907314117035131618062582953512203870615406642787786668571083042463072230605649134

p=gcd(g1-1,N)
print(gcd(g1-1,N))
q=N//p
c1=c1%p
c2=c2%q
print(long_to_bytes(c1))
print(c1.bit_length())
#b'flag{f561fafb-32ce-9d'
S= 234626762558445335519229319778735528295
print(S.bit_length())
N= 28053749721930780797243137464055357921262616541619976645795810707701031602793034889886420385567169222962145128498131170577184276590698976531070900776293344109534005057067680663813430093397821366071365221453788763262381958185404224319153945950416725302184077952893435265051402645871699132910860011753502307815457636525137171681463817731190311682277171396235160056504317959832747279317829283601814707551094074778796108136141845755357784361312469124392408642823375413433759572121658646203123677327551421440655322226192031542368496829102050186550793124020718643243789525477209493783347317576783265671566724068427349961101
e= 5
Cs= [1693447496400753735762426750097282582203894511485112615865753001679557182840033040705025720548835476996498244081423052953952745813186793687790496086492136043098444304128963237489862776988389256298142843070384268907160020751319313970887199939345096232529143204442168808703063568295924663998456534264361495136412078324133263733409362366768460625508816378362979251599475109499727808021609000751360638976, 2240772849203381534975484679127982642973364801722576637731411892969654368457130801503103210570803728830063876118483596474389109772469014349453490395147031665061733965097301661933389406031214242680246638201663845183194937353509302694926811282026475913703306789097162693368337210584494881249909346643289510493724709324540062077619696056842225526183938442535866325407085768724148771697260859350213678910949, 5082341111246153817896279104775187112534431783418388292800705085458704665057344175657566751627976149342406406594179073777431676597641200321859622633948317181914562670909686170531929552301852027606377778515019377168677204310642500744387041601260593120417053741977533047412729373182842984761689443959266049421034949822673159561609487404082536872314636928727833394518122974630386280495027169465342976]

cnt=3
A = [(i + 128) ** 2 for i in range(cnt)]
B = [(i + 1024) for i in range(cnt)]
C = [(i + 512) for i in range(cnt)]
test=A[0]*S**2+B[0]*S+C[0]
test=pow(test,5)
print(test.bit_length())
for i in range(cnt):
    print(iroot(Cs[i],5))
    Cs[i]=int(iroot(Cs[i],5)[0])
print(Cs)
from z3 import *


m1=BitVec('m1',128)
m2=BitVec('m2',128)
m3=BitVec('m3',128)
s=Solver()
s.add(m1+m2+m3==S)
s.add(((A[0] * m1 *m1 + B[0] * m1 + C[0]))==Cs[0])
s.add(((A[1] * m2 *m2 + B[1] * m2 + C[1]))==Cs[1])
s.add(((A[2] * m3 *m3 + B[2] * m3 + C[2]))==Cs[2])
print(s.check())
print(s.model())
'''
m3 = 36029897673981719660827899610422516507,
m1 = 65413472431888815878902893901773169457,
m2 = 133183392452574799979498526266539842331
'''
m3 = 36029897673981719660827899610422516507
m1 = 65413472431888815878902893901773169457
m2 = 133183392452574799979498526266539842331
print(long_to_bytes(m1))
print(long_to_bytes(m2))
print(long_to_bytes(m3))
#b'16-18fa-ec795fc1'
#b'd208}
#flag{f561fafb-32ce-9d16-18fa-ec795fc1d208}
exit()